/*
 * \brief  AVL tree
 * \author Norman Feske
 * \date   2006-04-12
 */

/*
 * Copyright (C) 2006-2009 Norman Feske
 * Genode Labs, Feske & Helmuth Systementwicklung GbR
 *
 * This file is part of the Genode OS framework, which is distributed
 * under the terms of the GNU General Public License version 2.
 */

#ifndef _INCLUDE__UTIL__AVL_TREE_H_
#define _INCLUDE__UTIL__AVL_TREE_H_

#include <util/misc_math.h>
#include <base/printf.h>

namespace Genode {

	/**
	 * AVL node
	 *
	 * \param NT  type of the class derived from 'Avl_node'
	 *
	 * Each object to be stored in the avl tree must be derived from
	 * 'Avl_node'. The type of the derived class is to be specified as
	 * template argument to enable 'Avl_node' to call virtual functions
	 * specific for the derived class.
	 */
	template <typename NT>
	class Avl_node
	{
		protected:

			enum { LEFT = false, RIGHT = true };

			Avl_node     *_child[2];  /* left and right subtrees */
			Avl_node     *_parent;    /* parent of subtree       */
			unsigned char _depth;     /* depth of subtree        */

		private:

			typedef bool Side;

			/**
			 * Determine depth of subtree
			 */
			inline int _child_depth(Side i) {
				return _child[i] ? _child[i]->_depth : 0; }

			/**
			 * Update depth of node
			 */
			inline void _recompute_depth()
			{
				unsigned char old_depth = _depth;
				_depth = max(_child_depth(LEFT), _child_depth(RIGHT)) + 1;

				/* if our own value changes, update parent */
				if (_depth != old_depth && _parent)
					_parent->_recompute_depth();

				/* call recompute hook only for valid tree nodes */
				if (_parent)
					static_cast<NT *>(this)->recompute();
			}

			/**
			 * Determine left-right bias of both subtrees
			 */
			inline Side _bias() {
				return (_child_depth(RIGHT) > _child_depth(LEFT)); }

			/**
			 * Insert subtree into specified side of the node
			 */
			void _adopt(Avl_node *node, Side i)
			{
				_child[i] = node;
				if (node)
					node->_parent = this;

				_recompute_depth();
			}

			/**
			 * Rotate subtree
			 *
			 * \param side   direction of rotate operation
			 * \param node   subtree to rotate
			 *
			 * The local node_* variable names describe node locations for
			 * the left (default) rotation. For example, node_r_l is the
			 * left of the right of node.
			 */
			void _rotate_subtree(Avl_node *node, Side side = LEFT)
			{
				int i = (node == _child[0]) ? LEFT : RIGHT;

				Avl_node *node_r   = node->_child[!side];
				Avl_node *node_r_l = node_r->_child[side];

				/* simple rotation */
				if (node_r->_bias() == !side) {

					node->_adopt(node_r_l, !side);
					node_r->_adopt(node, side);

					_adopt(node_r, i);
				}

				/* double rotation */
				else if (node_r_l) {

					Avl_node *node_r_l_l = node_r_l->_child[side];
					Avl_node *node_r_l_r = node_r_l->_child[!side];

					node->_adopt(node_r_l_l, !side);
					node_r->_adopt(node_r_l_r, side);

					node_r_l->_adopt(node, side);
					node_r_l->_adopt(node_r, !side);

					_adopt(node_r_l, i);
				}
			}

			/**
			 * Rebalance subtree
			 *
			 * \param node   immediate child that needs balancing
			 *
			 * 'this' is parent of the subtree to rebalance
			 */
			void _rebalance_subtree(Avl_node *node)
			{
				int v = node->_child_depth(RIGHT) - node->_child_depth(LEFT);

				/* return if subtree is in balance */
				if (abs(v) < 2) return;

				_rotate_subtree(node, (v < 0));
			}

		public:

			/**
			 * Constructor
			 */
			Avl_node() : _parent(0), _depth(1) {
				_child[LEFT] = _child[RIGHT] = 0; }

			/**
			 * Compare two nodes
			 *
			 * \retval false if n is lower than this
			 * \retval true  if n is higher than or equal to 'this'
			 *
			 * This function must be provided by the derived class.
			 * It determines the order of nodes inside the avl tree.
			 */
			bool higher(NT *n) const;

			/**
			 * Node recomputation hook
			 *
			 * If a node gets rearranged, this function is called.
			 * It can be used to update avl-tree-position dependent
			 * meta data.
			 */
			void recompute() { }

			/**
			 * Insert new node into subtree
			 */
			void insert(Avl_node *node)
			{
				if (node == this) {
					PERR("Inserting element %p twice into avl tree!", node);
					return;
				}

				Side i = LEFT;

				/* for non-root nodes, decide for a branch */
				if (_parent)
					i = static_cast<NT *>(this)->higher(static_cast<NT *>(node));

				if (_child[i])
					_child[i]->insert(node);
				else
					_adopt(node, i);

				/* the inserted node might have changed the depth of the subtree */
				_recompute_depth();

				if (_parent)
					_parent->_rebalance_subtree(this);
			}

			/**
			 * Remove node from tree
			 */
			void remove()
			{
				Avl_node *lp = 0;
				Avl_node *l  = _child[0];

				if (l) {

					/* find right-most node in left sub tree (l) */
					while (l && l->_child[1])
						l = l->_child[1];

					/* isolate right-most node in left sub tree */
					if (l == _child[0])
						_adopt(l->_child[0], LEFT);
					else
						l->_parent->_adopt(l->_child[0], RIGHT);

					/* consistent state */

					/* remember for rebalancing */
					if (l->_parent != this)
						lp = l->_parent;

					/* exchange this and l */
					for (int i = 0; i < 2; i++)
						if (_parent->_child[i] == this)
							_parent->_adopt(l, i);

					l->_adopt(_child[0], LEFT);
					l->_adopt(_child[1], RIGHT);

				} else {

					/* no left sub tree, attach our right sub tree to our parent */
					for (int i = 0; i < 2; i++)
						if (_parent->_child[i] == this)
							_parent->_adopt(_child[1], i);
				}

				/* walk the tree towards its root and rebalance sub trees */
				while (lp && lp->_parent) {
					Avl_node *lpp = lp->_parent;
					lpp->_rebalance_subtree(lp);
					lp = lpp;
				}
			}

			/**
			 * Request children of node
			 */
			inline NT *child(Side i) const { return static_cast<NT *>(_child[i]); }
	};


	/**
	 * Root node of the AVL tree
	 *
	 * The real nodes are always attached at the left branch of
	 * this root node.
	 */
	template <typename NT>
	class Avl_tree : public Avl_node<NT>
	{
		public:

			bool higher(NT *n1) const { return false; }

			/**
			 * Request first node of the tree
			 *
			 * \return  first node
			 * \retval  NULL if tree is empty
			 */
			inline NT *first() const { return child(Avl_node<NT>::LEFT); }
	};
}


#endif /* _INCLUDE__UTIL__AVL_TREE_H_ */
